Die Blasensortierung ist einer der einfachsten Sortieralgorithmen, der das gegebene Array durchläuft und benachbarte Elemente vergleicht. Wenn die Elemente in der falschen Reihenfolge sind, werden sie vertauscht, um sie in die richtige Reihenfolge zu bringen. Dieser Vorgang wird fortgesetzt, bis das gesamte Array sortiert ist.
Algorithmus:
Schritt 1:Das Array mehrmals durchlaufen
Vergleichen Sie in jeder Iteration benachbarte Elemente (i und i + 1).
Schritt 2:Wenn das aktuelle Element (i) größer als das nächste Element (i + 1) ist, tauschen Sie sie aus
Wiederholen Sie diesen Vorgang, bis das gesamte Array sortiert ist
Zeitkomplexität:
O(n^2), da es das Array mehrmals durchläuft und in jeder Iteration Vergleiche und Austauschvorgänge durchführt.
Codebeispiel in Python:
def bubble_sort(arr):
für i in range(len(arr) - 1):
# Durchlaufen Sie das Array, um benachbarte Elemente zu vergleichen
für j im Bereich(len(arr) - 1 - i):
# Vergleichen Sie das aktuelle Element mit dem nächsten Element
wenn arr[j]> arr[j + 1]:
# Vertauschen Sie die Elemente, wenn sie in der falschen Reihenfolge sind
arr[j], arr[j + 1] =arr[j + 1], arr[j]
# Gibt das sortierte Array zurück
Rückkehr ank
Beispiel:
Eingang:
[5, 3, 1, 2, 4]
Ausgabe:
[1, 2, 3, 4, 5]
Der Blasensortierungsalgorithmus durchläuft das Array und vergleicht benachbarte Elemente. Wenn sie in der falschen Reihenfolge sind, werden sie vertauscht. Dieser Vorgang wird wiederholt, bis das gesamte Array sortiert ist.
So funktioniert der Algorithmus in diesem Beispiel:
Iteration 1:
- Vergleichen Sie 5 und 3:Vertauschen Sie sie, da 5 größer als 3 ist.
- Vergleichen Sie 3 und 1:Vertauschen Sie sie, da 3 größer als 1 ist.
- Vergleichen Sie 2 und 4:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Array wird zu:[3, 1, 2, 4, 5].
Iteration 2:
- Vergleichen Sie 3 und 1:Vertauschen Sie sie, da 3 größer als 1 ist.
- Vergleichen Sie 1 und 2:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Vergleichen Sie 2 und 4:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Array wird zu:[1, 2, 3, 4, 5].
Iteration 3:
- Vergleichen Sie 1 und 2:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Vergleichen Sie 2 und 3:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Vergleichen Sie 3 und 4:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Array wird zu:[1, 2, 3, 4, 5].
Iteration 4:
- Vergleichen Sie 1 und 2:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Vergleichen Sie 2 und 3:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Vergleichen Sie 3 und 4:Kein Austausch erforderlich, da sie in der richtigen Reihenfolge sind.
- Array bleibt unverändert.
Nach der vierten Iteration wird das Array in aufsteigender Reihenfolge sortiert:[1, 2, 3, 4, 5].
